0%

Self-Learned Algorithms - 03

Posted on Edited on In

Self-Learned Algorithms - 03

This is my learning note about algorithms.

Reference

70.爬楼梯

https://leetcode-cn.com/problems/climbing-stairs/

题解

  • 很简单的dp题，不过在评论区找到很多有意思的解法

解法

  • 递归法：容易超时，python可以加个缓存装饰器
1
2
3
4
5
@functools.lru_cache(100)  # 缓存装饰器
def climbStairs(self, n: int) -> int:
  if n == 1: return 1
  if n == 2: return 2
  return self.climbStairs(n-1) + self.climbStairs(n-2)
  • DP1：新建一个字典或者数组来存储以前的变量，空间复杂度O(n)
1
2
3
4
5
6
dp = {}
dp[1] = 1
dp[2] = 2
for i in range(3,n+1):
	dp[i] = dp[i-1] + dp[i-2]
return dp[n]
  • DP2：只存储前两个元素，减少了空间，空间复杂度O(1)
1
2
3
4
5
if n < 3: return n
a, b = 1, 2
for i in range(3,n+1):
  a,b = b,a + b
return b
  • 斐波那契数列
1
2
3
4
import math
sqrt5=5**0.5
fibin=math.pow((1+sqrt5)/2,n+1)-math.pow((1-sqrt5)/2,n+1)
return int(fibin/sqrt5)
  • 面向测试用例编程（笑死）
1
2
a = [1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903]
return a[n-1]
  • 利用排列组合C(n,m)=n!/m!(n-m)!，可参考该解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def fac(self, num):
  factorial = 1
  for i in range(1,num + 1):
    factorial = factorial * i
  return factorial

def climbStairs(self, n: int) -> int:
  twostep = 0
  maxtwo = n //2
  j = 0
  while twostep <= maxtwo:
    onestep = n - 2 * twostep
    m = onestep + twostep
    j = j + self.fac(m)//(self.fac(onestep) * self.fac(twostep))
    twostep += 1
  return j

53.最大子序和

https://leetcode-cn.com/problems/maximum-subarray/

题解

  • 设定状态dp[i]为以nums[i]为结尾的连续子数组最大和
  • 结果为i的情况下nums[i]必定为正数
  • 如果dp[i-1]为负数，那么dp[i]=nums[i]

解法

  • 一边遍历一边计算：nums[i-1]并不是数组前一项的意思，而是到前一项为止的最大子序和，和0比较是因为只要大于0，就可以相加构造最大子序和。
1
2
3
for i in range(1, len(nums)):
	nums[i] = nums[i] + max(nums[i-1], 0)
return max(nums)
  • 正经dp
1
2
3
4
5
6
dp = nums[:]
res = dp[0]
for i in range(1, len(nums)):
	dp[i] = max(nums[i], nums[i] + dp[i - 1])
	res = max(res, dp[i])
return res

简化版：只用一个值保存结果

1
2
3
4
5
6
pre = nums[0]
res = pre
for i in range(1, len(nums)):
	dp[i] = max(nums[i], nums[i] + pre)
	res = max(res, pre)
return res

300.最长上升子序列

https://leetcode-cn.com/problems/longest-increasing-subsequence/

题解

  • LIS可能是连续的，也可能是非连续的（不严格审题以为$O(N)$能解决的）
  • “上升”是“严格上升”，类似于 [2, 3, 3, 6, 7] 这样的子序列是不符合要求的

解法

  • 动态规划：dp[i]的值代表以nums[i] 为结尾的最长子序列长度，每轮计算新dp[i]时，遍历[0,i)列表区间。时间复杂度$O(N^2)$。
1
2
3
4
5
6
7
if not nums: return 0
dp = [1] * len(nums)
for i in range(len(nums)):
  for j in range(i):
    if nums[j] < nums[i]: # 如果要求非严格递增，将此行 '<' 改为 '<=' 即可。
    	dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
  • 二分查找：是否可以通过重新设计状态定义，使整个dp为一个排序列表；这样在计算每个dp[k]时，就可以通过二分法遍历[0,k)区间元素，将此部分复杂度由$O(N)$降至$O(logN)$。
1
2
3
4
5
6
7
8
9
10
tails, res = [0] * len(nums), 0
for num in nums:
	i, j = 0, res
  while i < j:
    m = (i + j) // 2
    if tails[m] < num: i = m + 1 # 如果要求非严格递增，将此行 '<' 改为 '<=' 即可。
    else: j = m
  tails[i] = num
  if j == res: res += 1
return res

二分查找的运行时间居然比普通动态规划的快20倍，惊了！

120.三角形最小路径和

https://leetcode-cn.com/problems/triangle/

题解

  • 常规动态规划题目，需要考虑一下边界的问题。从上到下和从下到上都可以做。

解法

  • 运气解法（又名reinforcement learning）（笑死）：随机的瞎走，走上个10000遍，只保留步数最小的那一个
1
2
3
4
5
6
7
8
9
10
sum = 9999999
运气指数 = 10000 #这个看你的运气了，运气好1次通过，运气不好99999999都过不了
for i in range(运气指数):
  step = 0
  pos = 0
  for j in range(len(t)):
    step += t[j][pos]
    pos += random.choice([0,1]) #随机的选择下一次的方向
  sum = min(step,sum)
return sum
  • 原地修改自底而上
1
2
3
4
for i in range(len(triangle) - 1, 0, -1):
  for j in range(i):
  	triangle[i - 1][j] += min(triangle[i][j], triangle[i][j + 1])
return triangle[0][0]
  • 自上而下：状态转移方程中的dp[i-1][j-1]中的j-1，当j=0时，其效果等同于dp[i-1][-1]，即无穷大值float('inf')；同理，j=i时dp[i-1][j]也表示无穷大值，因此不需要再进行边界判别。
1
2
3
4
5
6
dp = [[float('inf')] * len(triangle) for _ in range(len(triangle))]
dp[0][0] = triangle[0][0]
for i in range(1,len(triangle)):
  for j in range(i+1):            
    dp[i][j] = min(dp[i-1][j-1]+triangle[i][j], dp[i-1][j]+triangle[i][j])
return min(dp[-1])

64.最小路径和

https://leetcode-cn.com/problems/minimum-path-sum/

题解

  • 和上一道题差不多，状态转移也只有两个。
  • （思考题）路径和类问题和之前的子序列类问题有何区别？

解法

  • 在原数组上进行记忆
1
2
3
4
5
6
7
8
9
10
11
for i in range(len(grid)):
  for j in range(len(grid[0])):
    if i==0 and j==0: #起点
    	continue
    elif i==0: #左边缘
    	grid[i][j] = grid[i][j-1] + grid[i][j]
    elif j==0: #上边缘
    	grid[i][j] = grid[i-1][j] + grid[i][j]
    else: #普遍情况
    	grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j]
return grid[-1][-1]
  • 反向动态规划：边界条件与正向相似
1
2
3
4
5
6
7
8
9
10
x = len(grid[0])
y = len(grid)
for i in range(x-2, -1, -1):
	grid[-1][i] += grid[-1][i+1]
for i in range(y-2, -1, -1):
	grid[i][-1] += grid[i+1][-1]
for i in range(y-2, -1, -1):
  for j in range(x-2, -1, -1):
  	grid[i][j] += min(grid[i][j+1], grid[i+1][j])
return grid[0][0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
dct = {}
xx = len(grid)
yy = len(grid[0])

def dfs(x: int, y: int) -> int:
  if (x, y) in dct:
  	return dct[(x, y)]
  if x == xx or y == yy:
  	return float("inf")
  p = min(dfs(x+1, y), dfs(x, y+1))
  dct[(x, y)] = grid[x][y]+(0 if p == float("inf") else p)
  return dct[(x, y)]

return dfs(0, 0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
dct = defaultdict(lambda: float("inf"))
xx = len(grid)
yy = len(grid[0])
deq = deque([(xx-1, yy-1)])
while deq:
  x, y = deq.popleft()
  if (x, y) in dct:
  	continue
  if x < 0 or y < 0:
  	continue
  p = min(dct[(x+1, y)], dct[(x, y+1)])
  deq.extend([(x-1, y), (x, y-1)])
  dct[(x, y)] = grid[x][y]+(0 if p == float("inf") else p)
return dct[(0, 0)]

两种记忆化搜索还需要再详细思考一下

198.打家劫舍

https://leetcode-cn.com/problems/house-robber/

题解

  • 失业程序员转职做小偷（？）

解法

  • 动态规划
1
2
3
4
5
6
if len(nums) == 0: return 0
dp = [0] * (len(nums) + 1)
dp[1] = nums[0]
for i in range(2, N+1):
	dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])
return dp[N]

空间优化（奇怪的是时间减半但内存消耗增加了）

1
2
3
4
5
6
7
8
prev = 0
curr = 0
for i in nums:
  # 循环开始时，curr 表示 dp[k-1]，prev 表示 dp[k-2]
  # dp[k] = max{ dp[k-1], dp[k-2] + i }
  prev, curr = curr, max(curr, prev + i)
  # 循环结束时，curr 表示 dp[k]，prev 表示 dp[k-1]
return curr